{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Best Team With No Conflicts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: bestTeamScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #无矛盾的最佳球队"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 <strong>总和</strong> 。</p>\n",
    "\n",
    "<p>然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 <strong>没有矛盾</strong> 的球队。如果一名年龄较小球员的分数 <strong>严格大于</strong> 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。</p>\n",
    "\n",
    "<p>给你两个列表 <code>scores</code> 和 <code>ages</code>，其中每组 <code>scores[i]</code> 和 <code>ages[i]</code> 表示第 <code>i</code> 名球员的分数和年龄。请你返回 <strong>所有可能的无矛盾球队中得分最高那支的分数</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>scores = [1,3,5,10,15], ages = [1,2,3,4,5]\n",
    "<strong>输出：</strong>34\n",
    "<strong>解释：</strong>你可以选中所有球员。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>scores = [4,5,6,5], ages = [2,1,2,1]\n",
    "<strong>输出：</strong>16\n",
    "<strong>解释：</strong>最佳的选择是后 3 名球员。注意，你可以选中多个同龄球员。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>scores = [1,2,3,5], ages = [8,9,10,1]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>最佳的选择是前 3 名球员。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= scores.length, ages.length &lt;= 1000</code></li>\n",
    "\t<li><code>scores.length == ages.length</code></li>\n",
    "\t<li><code>1 &lt;= scores[i] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>1 &lt;= ages[i] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [best-team-with-no-conflicts](https://leetcode.cn/problems/best-team-with-no-conflicts/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [best-team-with-no-conflicts](https://leetcode.cn/problems/best-team-with-no-conflicts/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,5,10,15]\\n[1,2,3,4,5]', '[4,5,6,5]\\n[2,1,2,1]', '[1,2,3,5]\\n[8,9,10,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        # nums = list(zip(scores, ages))\n",
    "        # nums.sort()\n",
    "        # n = len(nums)\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i):\n",
    "        #     ans= 0\n",
    "        #     for j in range(i):\n",
    "        #         if nums[j][1] <= nums[i][1]:\n",
    "        #             ans = max(ans, dfs(j))\n",
    "        #     ans += nums[i][0]\n",
    "        #     return ans\n",
    "        \n",
    "        # return max(dfs(i) for i in range(n))\n",
    "\n",
    "        # nums = sorted(zip(scores, ages))\n",
    "        # f = [0] * len(nums)\n",
    "        # for i, (score, age) in enumerate(nums):\n",
    "        #     for j in range(i):\n",
    "        #         if nums[j][1] <= age:\n",
    "        #             f[i] = max(f[i], f[j])\n",
    "        #     f[i] += score\n",
    "        # return max(f)\n",
    "\n",
    "        max_sum = [0] * (max(ages) + 1)\n",
    "        for score, age in sorted(zip(scores, ages)):\n",
    "            max_sum[age] = max(max_sum[:age+1]) + score\n",
    "        return max(max_sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        n = len(scores)\n",
    "        s = sorted(zip(scores, ages))\n",
    "        dp = [0] * (n)\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if s[j][1] <= s[i][1]:\n",
    "                    dp[i] = max(dp[i], dp[j])\n",
    "            dp[i] += s[i][0]\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        n = len(scores)\n",
    "        people = sorted(zip(scores, ages))\n",
    "        dp = [0] * len(scores)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if people[i][1] >= people[j][1]:\n",
    "                    dp[i] = max(dp[i], dp[j])\n",
    "            dp[i] += people[i][0]\n",
    "            res = max(res, dp[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        max_sum = [0] * (max(ages) + 1)\n",
    "        for score, age in sorted(zip(scores, ages)):\n",
    "            max_sum[age] = max(max_sum[:age + 1]) + score\n",
    "        return max(max_sum)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        # 从值域考虑\n",
    "        maxsum = [0] * (max(ages) + 1)\n",
    "        for score, age in sorted(zip(scores, ages)):\n",
    "            maxsum[age] = max(maxsum[:age + 1]) + score\n",
    "        return max(maxsum)\n",
    "\n",
    "        # 递推\n",
    "        # nums = sorted(zip(scores, ages))\n",
    "        # n = len(nums)\n",
    "        # f = [0] * n\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i):\n",
    "        #         if nums[j][1] <= nums[i][1]:\n",
    "        #             f[i] = max(f[i], f[j])\n",
    "        #     f[i] += nums[i][0]\n",
    "        # return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        n = len(scores)\n",
    "        a = sorted(zip(scores,ages))\n",
    "        f = [0]*n\n",
    "        # score 从小到大\n",
    "        for i,(score,age) in enumerate(a):\n",
    "            f[i] = score\n",
    "            for j in range(i):\n",
    "                if a[j][1] <= age: # 分数更小，年龄不能更大\n",
    "                    f[i] = max(f[i],f[j] + score)\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        members = list(zip(ages, scores))\n",
    "        members.sort()\n",
    "\n",
    "        n = len(members)\n",
    "        ans = 0\n",
    "        dp = [0] * n\n",
    "        for i in range(n):\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if members[j][1] <= members[i][1]:\n",
    "                    dp[i] = max(dp[i], dp[j])\n",
    "            dp[i] += members[i][1]\n",
    "            ans = max(ans, dp[i])\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        n = len(scores)\n",
    "        a = sorted(zip(scores,ages))\n",
    "        \n",
    "        f = [0]*1001\n",
    "        for sc,age in a:\n",
    "            f[age] = max(f[:age + 1]) + sc\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        u = max(ages)\n",
    "        t = [0] * (u + 1)\n",
    "\n",
    "        def query(i: int)->int:\n",
    "            mx = 0\n",
    "            while i:\n",
    "                mx = max(mx, t[i])\n",
    "                i &= i - 1\n",
    "            return mx\n",
    "\n",
    "        def update(i: int, mx: int)->None:\n",
    "            while i < len(t):\n",
    "                t[i] = max(t[i], mx)\n",
    "                i += i & -i\n",
    "\n",
    "        for score, age in sorted(zip(scores, ages)):\n",
    "            update(age, query(age) + score)\n",
    "        \n",
    "        return query(u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        n=len(scores)\n",
    "        pers=[(scores[i],ages[i]) for i in range(n)]\n",
    "        pers.sort()\n",
    "        dp=[0]*(n)\n",
    "        dp[0]=pers[0][0]\n",
    "        for i in range(1,n):\n",
    "            for j in range(0,i):\n",
    "                if pers[j][1]<=pers[i][1]:\n",
    "                    dp[i]=max(dp[i],dp[j])\n",
    "            dp[i]+=pers[i][0]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        people = sorted(zip(scores, ages))\n",
    "        dp = [0] * len(scores)\n",
    "        ans = 0\n",
    "        for i in range(len(scores)):\n",
    "            for j in range(i):\n",
    "                if people[i][1] >= people[j][1]:\n",
    "                    dp[i] = max(dp[i], dp[j])\n",
    "            dp[i] += people[i][0]\n",
    "            ans = max(ans, dp[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        n = len(scores)\n",
    "        def cmp(a,b):\n",
    "            if a[1] != b[1]:\n",
    "                return a[1]-b[1]\n",
    "            else:\n",
    "                return a[0]-b[0]\n",
    "        players = sorted(zip(ages, scores), key = cmp_to_key(cmp))\n",
    "        dp = [ [0]*1001 ]*n\n",
    "        for i in range(1,1001):\n",
    "            dp[0][i] = players[0][1] if players[0][0] <= i else 0\n",
    "\n",
    "        for indx in range(1,n):\n",
    "            for age in range(1000, 0, -1):\n",
    "                dp[indx][age] = dp[indx-1][age]\n",
    "                if players[indx][0] <= age:\n",
    "                    dp[indx][age] = max(dp[indx][age], players[indx][1] + dp[indx-1][players[indx][0]])\n",
    "        return dp[n-1][1000]\n",
    "\n",
    "        # @cache #indx之前，不超过age的最大分数\n",
    "        # def f(indx, age):\n",
    "        #     if indx == 0:\n",
    "        #         return players[indx][1] if players[indx][0] <= age else 0\n",
    "        #     res = f(indx-1, age)\n",
    "        #     if players[indx][0] <= age:\n",
    "        #         res = max(res, players[indx][1]+f(indx-1, players[indx][0]))\n",
    "        #     return res\n",
    "        # return f(n-1, 1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        a = sorted(zip(scores, ages))\n",
    "        f = [0] * len(a)\n",
    "        for i, (score, age) in enumerate(a):\n",
    "            for j in range(i):\n",
    "                if a[j][1] <= age:\n",
    "                    f[i] = max(f[i], f[j])\n",
    "            f[i] += score\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        n=len(scores)\n",
    "        dp=[0]*(n)\n",
    "        pers=[(scores[i],ages[i]) for i in range(n)]\n",
    "        pers.sort()\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if pers[i][1]>=pers[j][1]:\n",
    "                    dp[i]=max(dp[i],dp[j])\n",
    "            dp[i]+=pers[i][0]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        a = sorted(zip(scores, ages))\n",
    "        f = [0] * len(a)\n",
    "        for i, (score, age) in enumerate(a):\n",
    "            for j in range(i):\n",
    "                if a[j][1] <= age:\n",
    "                    f[i] = max(f[i], f[j])\n",
    "            f[i] += score\n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        nums = sorted(zip(scores,ages)) #分数从小到大排序，分数相同的按照年龄从小到大排序\n",
    "        n = len(nums)\n",
    "        f = [0]*n\n",
    "        for i, (score, age) in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                if nums[j][1] <= age:\n",
    "                    f[i] = max(f[i],f[j])\n",
    "            f[i] += score\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        perlist = []\n",
    "        n = len(scores)\n",
    "        for i in range(n):\n",
    "            perlist.append((ages[i], scores[i]))\n",
    "        perlist.sort(key=lambda x:(x[0], x[1]))\n",
    "        # lenu = len(unqscores)\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        maxval = [0 for _ in range(n+1)]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            agei, sci = perlist[i]\n",
    "            dp[i] = sci\n",
    "            maxval[i] = sci\n",
    "            ans = max(ans, sci)\n",
    "            for j in range(i):\n",
    "                agej, scj = perlist[i]\n",
    "                if sci >= maxval[j]:\n",
    "                    dp[i] = max(dp[i], dp[j]+sci)\n",
    "                    maxval[i] = max(maxval[j], maxval[i])\n",
    "                    ans = max(ans, dp[i])\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "\n",
    "        n=len(scores)\n",
    "        arr=[]\n",
    "        for i in range(n):\n",
    "            arr.append([ages[i],scores[i]])\n",
    "        arr.sort(key=lambda x:[x[0],x[1]])\n",
    "        dp=[0]*n\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[i]=arr[i][1]\n",
    "        for i in range(1,n):\n",
    "            age1=arr[i][0]\n",
    "            score1=arr[i][1]\n",
    "            for j in range(i-1,-1,-1):\n",
    "                age2=arr[j][0]\n",
    "                score2=arr[j][1]\n",
    "                if (age1>age2 and score1>=score2) or (age1==age2): \n",
    "                    dp[i]=max(dp[i],dp[j]+score1)\n",
    "      #  print(arr)\n",
    "        #print(dp)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "\n",
    "        n = len(scores)\n",
    "        a = sorted(zip(scores, ages), key=lambda x: (x[1], x[0]))\n",
    "        # print(a)\n",
    "        dp = [0] * n\n",
    "        for i in range(n):\n",
    "            dp[i] = a[i][0]\n",
    "            for j in range(i):\n",
    "                if a[j][0] <= a[i][0]:\n",
    "                    dp[i] = max(dp[i], dp[j] + a[i][0])\n",
    "        # print(dp)\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        perlist = []\n",
    "        n = len(scores)\n",
    "        for i in range(n):\n",
    "            perlist.append((ages[i], scores[i]))\n",
    "        perlist.sort(key=lambda x:(x[0], x[1]))\n",
    "        unqscores = list(set(scores))\n",
    "        lenu = len(unqscores)\n",
    "        numdict = {unqscores[i]:i for i in range(lenu)}\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        maxval = [0 for _ in range(n+1)]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            agei, sci = perlist[i]\n",
    "            dp[i] = sci\n",
    "            maxval[i] = sci\n",
    "            ans = max(ans, sci)\n",
    "            for j in range(i):\n",
    "                agej, scj = perlist[i]\n",
    "                if sci >= maxval[j]:\n",
    "                    dp[i] = max(dp[i], dp[j]+sci)\n",
    "                    maxval[i] = max(maxval[j], maxval[i])\n",
    "                    ans = max(ans, dp[i])\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        n = len(scores)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key = lambda x:(ages[x],scores[x]))\n",
    "        print(idx)\n",
    "        dp = [-inf]*n\n",
    "        dp[0] = scores[idx[0]]\n",
    "        ans = dp[0]\n",
    "        for i in range(1,n):\n",
    "            idxi = idx[i]\n",
    "            dp[i] = scores[idxi]\n",
    "            for j in range(i):\n",
    "                idxj = idx[j]\n",
    "                if scores[idxj]<=scores[idxi]:\n",
    "                    dp[i] = max(dp[i],dp[j]+scores[idxi])\n",
    "            ans = max(ans,dp[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        # 将球员组合起来并按年龄和得分进行排序\n",
    "        players = list(zip(scores, ages))\n",
    "        players.sort(key=lambda x: (x[1], x[0]))\n",
    "\n",
    "        # dp[i] 表示前 i 个球员中并选择第 i 个球员的最高得分\n",
    "        n = len(players)\n",
    "        dp = [0] * n\n",
    "        dp[0] = players[0][0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            # 最小得分就是第 i 位球员的得分\n",
    "            dp[i] = players[i][0]\n",
    "            for j in range(i):\n",
    "                # 确保没有矛盾\n",
    "                if players[j][0] <= players[i][0]:\n",
    "                    dp[i] = max(dp[i], dp[j] + players[i][0])\n",
    "\n",
    "        # 返回最高得分\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sorted(self, l, r):\n",
    "        if l > r:\n",
    "            return\n",
    "        i = l\n",
    "        j = r\n",
    "\n",
    "        while i<j:\n",
    "            while i<j and (self.ages[j] > self.ages[l] or (self.ages[j] == self.ages[l] and self.scores[j] > self.scores[l])):\n",
    "                j -= 1\n",
    "            while i<j and (self.ages[i] < self.ages[l] or (self.ages[i] == self.ages[l] and self.scores[i] <= self.scores[l])):\n",
    "                i += 1\n",
    "            if i<j:\n",
    "                self.ages[i], self.ages[j] = self.ages[j], self.ages[i]\n",
    "                self.scores[i], self.scores[j] = self.scores[j], self.scores[i]\n",
    "        \n",
    "        self.ages[i], self.ages[l] = self.ages[l], self.ages[i]\n",
    "        self.scores[i], self.scores[l] = self.scores[l], self.scores[i]\n",
    "\n",
    "        self.sorted(l, i-1)\n",
    "        self.sorted(i+1, r)\n",
    "\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        n = len(scores)\n",
    "\n",
    "        self.ages = ages\n",
    "        self.scores = scores\n",
    "\n",
    "        self.sorted(0, n-1)\n",
    "\n",
    "        dp = [0]*n\n",
    "        for i in range(n):\n",
    "            dp[i] = max(0, scores[i], *[dp[j]+((scores[i] if scores[i]>=scores[j] else -10**9) if ages[i] > ages[j] else scores[i]) for j in range(i)])\n",
    "\n",
    "        return max(0, *dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        nums = []\n",
    "        n = len(scores)\n",
    "        f = [0] * n\n",
    "        nums = list(zip(scores, ages))\n",
    "        print(nums)\n",
    "        nums.sort(key=lambda x: (x[0], x[1]))\n",
    "        print(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[j][1] <= nums[i][1]:\n",
    "                    f[i] = max(f[i], f[j])\n",
    "            f[i] += nums[i][0]\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        n = len(ages)\n",
    "        new_arr = []\n",
    "        for i in range(n):\n",
    "            temp = [scores[i], ages[i]]\n",
    "            new_arr.append(temp)\n",
    "\n",
    "        new_arr.sort(key=lambda x: (x[1], x[0]))\n",
    "        # print(new_arr)\n",
    "        new_scores = [m[0] for m in new_arr]\n",
    "        # print(new_scores)\n",
    "\n",
    "        # dp = [0] * n\n",
    "        # dp[0] = new_scores[0]\n",
    "\n",
    "        dp = [p for p in new_scores]\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if new_scores[i] >= new_scores[j]:\n",
    "                    dp[i] = max(dp[j] + new_scores[i], dp[i])\n",
    "        # print(dp)\n",
    "        # print(max(dp))\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        scores,ages = zip(*(sorted(zip(scores,ages),key = lambda x: (x[1],x[0]))))\n",
    "        scores,ages = list(scores), list(ages)\n",
    "        n = len(scores)\n",
    "        dp = scores.copy()\n",
    "        \n",
    "        for i in range(len(scores)):\n",
    "            for j in range(i):\n",
    "                if scores[j] <= scores[i]:\n",
    "                    dp[i] = max(dp[i], dp[j]+scores[i])\n",
    "        return max(dp)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        sorted_list = [(b, a) for a, b in zip(scores, ages)]\n",
    "        sorted_list.sort(key=lambda x:(x[0], x[1]))\n",
    "        def binary_search(arr, target):\n",
    "            l, r = 0, len(arr) - 1\n",
    "            while l <= r:\n",
    "                mid = (l+r) // 2\n",
    "                if arr[mid] < target:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            return l\n",
    "        \n",
    "        # d = [sorted_list[1]]\n",
    "        ans = sorted_list[0][1]\n",
    "        n = len(sorted_list)\n",
    "        f = [[0,0] for _ in range(n)]\n",
    "        # print(f)\n",
    "        # print(sorted_list)\n",
    "        for i in range(n):\n",
    "            f[i][0] = 1\n",
    "            f[i][1] = sorted_list[i][1]\n",
    "            for j in range(i):\n",
    "                if sorted_list[i][1] >= sorted_list[j][1]:\n",
    "                    if f[i][0] <= f[j][0] + 1:\n",
    "                        f[i][0] = f[j][0] + 1\n",
    "                        f[i][1] = max(f[j][1] + sorted_list[i][1], f[i][1])\n",
    "            ans = max(ans, f[i][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        n = len(scores)\n",
    "        sas = list(zip(scores, ages))\n",
    "        sas.sort(key=lambda x: (x[1], x[0]))\n",
    "        dp = [[sas[0][0]]*2]\n",
    "        maxscore = sas[0][0]\n",
    "        for s,a in sas[1:]:\n",
    "            ms = s\n",
    "            for i in range(len(dp)):\n",
    "                if dp[i][0] <= s:\n",
    "                    ms = max(ms, dp[i][1]+s)\n",
    "            dp.append([s,ms])\n",
    "            maxscore = max(maxscore, ms)\n",
    "\n",
    "        return maxscore\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        scores,ages = zip(*(sorted(zip(scores,ages),key = lambda x: (x[1],x[0]))))\n",
    "        scores,ages = list(scores), list(ages)\n",
    "        \n",
    "        print(scores,ages)\n",
    "        n = len(scores)\n",
    "        dp = scores.copy()\n",
    "        \n",
    "        for i in range(len(scores)):\n",
    "            for j in range(i):\n",
    "                if scores[j] <= scores[i]:\n",
    "                    dp[i] = max(dp[i], dp[j]+scores[i])\n",
    "        print(dp)\n",
    "        return max(dp)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        t=[[0,0]]+list(sorted(zip(ages,scores)))\n",
    "        def check(i,j):\n",
    "            return t[i][0]==t[j][0] or t[i][1]<=t[j][1]\n",
    "\n",
    "        @cache\n",
    "        def f(i):\n",
    "            nonlocal t\n",
    "            if i==len(t):\n",
    "                return 0\n",
    "            res=0\n",
    "            for j in range(i+1,len(t)):\n",
    "                if check(i,j):\n",
    "                    res=max(res,f(j))\n",
    "            return res+t[i][1]\n",
    "        return f(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        t=list(sorted(zip(ages,scores)))\n",
    "        def check(i,j):\n",
    "            nonlocal t\n",
    "            if t[i][0]==t[j][0]:\n",
    "                return True\n",
    "            else:\n",
    "                if t[i][1]<=t[j][1]:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "        @cache\n",
    "        def f(i):\n",
    "            nonlocal t\n",
    "            if i==len(t):\n",
    "                return 0\n",
    "            res=0\n",
    "            for j in range(i+1,len(t)):\n",
    "                if check(i,j):\n",
    "                    res=max(res,f(j))\n",
    "            return res+t[i][1]\n",
    "        res=0\n",
    "        for i in range(len(t)):\n",
    "            res=max(res,f(i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        t=[[0,0]]+list(sorted(zip(ages,scores)))\n",
    "        def check(i,j):\n",
    "            return t[i][0]==t[j][0] or t[i][1]<=t[j][1]\n",
    "\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i==len(t):\n",
    "                return 0\n",
    "            res=0\n",
    "            for j in range(i+1,len(t)):\n",
    "                if check(i,j):\n",
    "                    res=max(res,f(j))\n",
    "            return res+t[i][1]\n",
    "        return f(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        sa = sorted(zip(scores, ages))\n",
    "        n = len(sa)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            maxl = 0\n",
    "            for j in range(i + 1, n):\n",
    "                if sa[j][1] >= sa[i][1]:\n",
    "                    maxl = max(maxl, dfs(j) + sa[j][0])\n",
    "            return maxl\n",
    "        \n",
    "        return max(dfs(i) + sa[i][0] for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# name:Aoobex\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        people = sorted(zip(scores,ages))\n",
    "        n = len(scores)\n",
    "        @cache\n",
    "        def back_search(i):\n",
    "            score = people[i][0]\n",
    "            ans = 0\n",
    "            for j in range(i):\n",
    "                if people[j][1] <= people[i][1]:\n",
    "                    ans = max(ans,back_search(j))\n",
    "                else:\n",
    "                    if people[j][0] >= people[i][0]:\n",
    "                        ans = max(ans,back_search(j))\n",
    "            return ans+score\n",
    "\n",
    "        return max(back_search(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\r\n",
    "        from functools import lru_cache\r\n",
    "\r\n",
    "        # sort scores according to ages\r\n",
    "        players = sorted(zip(ages, scores))\r\n",
    "        n = len(scores)\r\n",
    "        \r\n",
    "        @lru_cache(n)\r\n",
    "        def lis(i):\r\n",
    "            ret = players[i][1]\r\n",
    "            for j in range(i):\r\n",
    "                if players[j][1] <= players[i][1]:\r\n",
    "                    ret = max(ret, lis(j) + players[i][1])\r\n",
    "            return ret\r\n",
    "        \r\n",
    "        return max(lis(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        n = len(scores)\n",
    "        players = [(ages[i], scores[i]) for i in range(n)]\n",
    "        players.sort() # 按年龄从小到大排序\n",
    "        memo = {} # 记忆化搜索\n",
    "        def dp(i):\n",
    "            if i in memo: # 如果该状态已经计算过\n",
    "                return memo[i]\n",
    "            res = players[i][1] # 初始化以第 i 名球员结尾的最大得分为该球员分数\n",
    "            for j in range(i):\n",
    "                if players[j][1] <= players[i][1]: # 判断是否存在矛盾\n",
    "                    res = max(res, dp(j) + players[i][1]) # 更新以第 i 名球员结尾的最大得分\n",
    "            memo[i] = res # 记录该状态的最大得分\n",
    "            return res\n",
    "        return max(dp(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# name:Aoobex\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        people = sorted(zip(scores,ages))\n",
    "        n = len(scores)\n",
    "        @cache\n",
    "        def back_search(i):\n",
    "            score = people[i][0]\n",
    "            ans = 0\n",
    "            for j in range(i):\n",
    "                if people[j][1] <= people[i][1]:\n",
    "                    ans = max(ans,back_search(j))\n",
    "                else:\n",
    "                    if people[j][0] >= people[i][0]:\n",
    "                        ans = max(ans,back_search(j))\n",
    "            return ans+score\n",
    "\n",
    "        return max(back_search(i) for i in range(n-1,-1,-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        \n",
    "        pairs = sorted(zip(ages, scores))\n",
    "        new_scores = [ele[1] for ele in pairs]\n",
    "        n = len(new_scores)\n",
    "\n",
    "        temp = [0]*n\n",
    "        def f(i):\n",
    "            res = 0\n",
    "\n",
    "            if temp[i] != 0:\n",
    "                return temp[i]\n",
    "\n",
    "            for j in range(i):\n",
    "                if new_scores[j] <= new_scores[i]:\n",
    "                    res = max(res, f(j))\n",
    "\n",
    "            temp[i] = res+new_scores[i]\n",
    "            return res + new_scores[i]\n",
    "\n",
    "        output = 0\n",
    "        for i in range(n):\n",
    "            output = max(output, f(i))\n",
    "\n",
    "        return output\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# f[i] = max(f[j]) + new_scores[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        n = len(scores)\n",
    "        players = [(ages[i], scores[i]) for i in range(n)]\n",
    "        players.sort() # 按年龄从小到大排序\n",
    "        memo = {} # 记忆化搜索\n",
    "        def dp(i):\n",
    "            if i in memo: # 如果该状态已经计算过\n",
    "                return memo[i]\n",
    "            res = players[i][1] # 初始化以第 i 名球员结尾的最大得分为该球员分数\n",
    "            for j in range(i):\n",
    "                if players[j][1] <= players[i][1]: # 判断是否存在矛盾\n",
    "                    res = max(res, dp(j) + players[i][1]) # 更新以第 i 名球员结尾的最大得分\n",
    "            memo[i] = res # 记录该状态的最大得分\n",
    "            return res\n",
    "        return max(dp(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        n = len(scores)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            cnt = 0\n",
    "            for j in range(i):\n",
    "                if nums[j][0] <= nums[i][0] and nums[j][1] <= nums[i][1]:\n",
    "                    cnt = max(cnt, dfs(j))\n",
    "            \n",
    "            return cnt + nums[i][1]\n",
    "        nums = []\n",
    "        for i in range(n):\n",
    "            nums.append([ages[i], scores[i]])\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, dfs(i))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "\n",
    "\n",
    "        # 方法一：dp 过了\n",
    "        # a = sorted(zip(scores, ages))\n",
    "        # n = len(ages)\n",
    "        # f = [0] * n\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i):\n",
    "        #         if a[i][1] >= a[j][1]:\n",
    "        #             f[i] = max(f[i], f[j])\n",
    "        #     f[i] += a[i][0]\n",
    "        # return max(f)\n",
    "\n",
    "        # 方法二：记忆化搜索 过了\n",
    "        a = sorted(zip(scores, ages))\n",
    "        n = len(ages)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            res = 0\n",
    "            for j in range(i):\n",
    "                if a[i][1] >= a[j][1]:\n",
    "                    res = max(res, dfs(j))\n",
    "            return res + a[i][0]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, dfs(i))\n",
    "        return ans\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        arr = list(zip(ages, scores))\n",
    "        arr.sort()\n",
    "        n = len(scores)\n",
    "\n",
    "        @cache\n",
    "        def dfs(idx: int) -> int:\n",
    "            if idx == 0:\n",
    "                return arr[idx][1]\n",
    "            res = 0\n",
    "            for j in range(idx):\n",
    "                if arr[j][1] <= arr[idx][1]:\n",
    "                    res = max(res, dfs(j))\n",
    "            return res + arr[idx][1]\n",
    "\n",
    "        return max(dfs(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        # a = sorted(zip(scores, ages))\n",
    "        # n = len(ages)\n",
    "        # f = [0] * n\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i):\n",
    "        #         if a[i][1] >= a[j][1]:\n",
    "        #             f[i] = max(f[i], f[j])\n",
    "        #     f[i] += a[i][0]\n",
    "        # return max(f)\n",
    "        a = sorted(zip(scores, ages))\n",
    "        n = len(ages)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            res = 0\n",
    "            for j in range(i):\n",
    "                if a[i][1] >= a[j][1]:\n",
    "                    res = max(res, dfs(j))\n",
    "            return res + a[i][0]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, dfs(i))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        arr = zip(scores, ages)\n",
    "        arr = sorted(arr)\n",
    "        n = len(scores)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            mx = 0\n",
    "            for j in range(i-1, -1, -1):            \n",
    "                if arr[i][1] >= arr[j][1]:\n",
    "                    mx = max(mx, dfs(j))\n",
    "            return mx + arr[i][0]\n",
    "        \n",
    "        return max( dfs(i) for i in range(n) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        people = list(zip(ages, scores))\n",
    "        people.sort()\n",
    "        n = len(people)\n",
    "        @lru_cache(None)\n",
    "        def f(i):\n",
    "            return max([0] + [f(j) for j in range(i + 1, n) if people[j][1] >= people[i][1]]) + people[i][1]\n",
    "        return max(f(i) for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        n = len(scores)\n",
    "        player = [(ages[i], scores[i]) for i in range(n)]\n",
    "        player.sort(key=lambda x: (-x[0], -x[1]))\n",
    "        \n",
    "        def check(last_age, last_score, cur_age, cur_score) -> bool:\n",
    "            if last_age == cur_age:\n",
    "                return True\n",
    "            return cur_score <= last_score\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(start, lastAge, lastScore) -> int:\n",
    "            if start == n:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for i in range(start, n):\n",
    "                cur_age, cur_score = player[i]\n",
    "                if check(lastAge, lastScore, cur_age, cur_score):\n",
    "                    res = max(res, cur_score + dfs(i + 1, cur_age, cur_score))\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, float('inf'), float('inf'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 子集型回溯 + 记忆化搜索\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        a = sorted(zip(scores, ages))\n",
    "        # dfs(i) 为排序后以 score_i 结尾的 LIS 最大长度\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            score_i, age_i = a[i]\n",
    "            res = 0\n",
    "            for j in range(i):\n",
    "                score_j, age_j = a[j]\n",
    "                if age_j <= age_i:\n",
    "                    res = max(res, dfs(j))\n",
    "            return res + score_i\n",
    "        return max(dfs(i) for i in range(len(scores)))\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "#         a = sorted(zip(scores, ages))\n",
    "#         f = [0] * len(a)\n",
    "#         for i, (score, age) in enumerate(a):\n",
    "#             for j in range(i):\n",
    "#                 if a[j][1] <= age:\n",
    "#                     f[i] = max(f[i], f[j])\n",
    "#             f[i] += score\n",
    "#         return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        \n",
    "        # No. 300 最长严格递增子序列 \n",
    "        sorted_t = sorted(zip(scores, ages)) # 按分数排序 相同分数按年龄排序 \n",
    "        # dp[i]为以序列号i结尾的最大的得分\n",
    "        # 动态规划的递归方程 dp[i] = max(dp[j]) + score[i] 约束条件 当score[j] = score[i]的时候， age[j] < age[i], 当score[j] < score[i] age[j] <= age[i] \n",
    "        # 约束条件是 只有在score一定是<= 的 只有在age\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            res = 0 \n",
    "            for j in range(i):\n",
    "                if sorted_t[j][1] <= sorted_t[i][1]:\n",
    "                    res = max(res, dfs(j)) \n",
    "            return res + sorted_t[i][0] \n",
    "        \n",
    "        return max(dfs(i) for i in range(len(sorted_t)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 子集型回溯 + 记忆化搜索\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        # 加上在原数组中的下标 i\n",
    "        scores = [[score, i] for i, score in enumerate(scores)]\n",
    "        scores.sort(key=lambda x: (x[0], ages[x[1]]))\n",
    "\n",
    "        # dfs(i) 为排序后以 scores[i] 结尾的 LIS 最大长度\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            score_i, index_i = scores[i]\n",
    "            res_score = 0\n",
    "            for j in range(i):\n",
    "                score_j, index_j = scores[j]\n",
    "                if ages[index_j] <= ages[index_i]:\n",
    "                    res_score = max(res_score, dfs(j))\n",
    "            return res_score + score_i\n",
    "\n",
    "        return max(dfs(i) for i in range(len(scores)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        # 把年龄按分数排序后，变成LIS问题\n",
    "        # 回溯+记忆化搜索\n",
    "        # 1 1 2 2\n",
    "        # 5 5 4 6\n",
    "        t = list(sorted(zip(scores, ages)))\n",
    "        n = len(t)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            res = 0\n",
    "            for j in range(i):\n",
    "                if t[j][1] <= t[i][1]:\n",
    "                    res = max(dfs(j), res)\n",
    "            return res + t[i][0]\n",
    "\n",
    "        return max(dfs(i) for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        n = len(scores)\n",
    "        scores = [[score, i] for i, score in enumerate(scores)]\n",
    "        scores.sort(key=lambda x: (x[0], ages[x[1]]))\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            score_i, index_i = scores[i]\n",
    "            res_score = 0\n",
    "            for j in range(i):\n",
    "                score_j, index_j = scores[j]\n",
    "                if ages[index_j] <= ages[index_i]:\n",
    "                    res_score = max(res_score, dfs(j))\n",
    "            return res_score + score_i\n",
    "\n",
    "        return max(dfs(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        arr = [(ages[i],scores[i]) for i in range(len(ages))]\n",
    "        arr.append((0,0))\n",
    "        arr.sort()\n",
    "        N = len(arr)\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx):\n",
    "            mx = 0\n",
    "            for i in range(idx+1,N):\n",
    "                if arr[i][0] > arr[idx][0] :\n",
    "                    if arr[i][1] >= arr[idx][1]:\n",
    "                        if mx < dfs(i) + arr[i][1]:\n",
    "                            mx = dfs(i) + arr[i][1]\n",
    "                else:\n",
    "                    if mx < dfs(i) + arr[i][1]:\n",
    "                        mx = dfs(i) + arr[i][1]\n",
    "            return mx\n",
    "        return dfs(0)\n",
    "        mx = 0\n",
    "        from  sortedcontainers import SortedList\n",
    "        dplist = SortedList()\n",
    "        for age, score in arr:\n",
    "            add = []\n",
    "            for i in range(len(dplist)):\n",
    "                if dplist[i][0] <= score:\n",
    "                    add.append( [score, age, dplist[i][2]+score] )\n",
    "                elif dplist[i][1] == age:\n",
    "                    add.append( [score, age, dplist[i][2]+score] )\n",
    "                else:\n",
    "                    break\n",
    "            dplist.add( [score,age,score] )\n",
    "            if score>mx:\n",
    "                mx = score\n",
    "            for ele in add:\n",
    "                dplist.add(ele)\n",
    "                if ele[2]>mx:\n",
    "                    mx = ele[2]\n",
    "        return mx\n",
    "\n",
    "\n",
    "\n",
    "        arr = []\n",
    "        for i,v in enumerate(ages):\n",
    "            arr.append( (v,scores[i]))\n",
    "        arr.sort()\n",
    "        n =  len(arr)\n",
    "        dp = [[0,0] for _ in range(n+1) ]\n",
    "        mx = 0\n",
    "        for i in range(n):\n",
    "            dp[i+1] = [arr[i][1],arr[i][1]] \n",
    "            for j in range(i,-1,-1):\n",
    "                if dp[j][1] <= arr[i][1]:\n",
    "                    if dp[i+1][0] < dp[j][0] + arr[i][1]:\n",
    "                        dp[i+1][0] = dp[j][0] + arr[i][1]\n",
    "            if mx < dp[i+1][0]:\n",
    "                mx = dp[i+1][0]\n",
    "        #print(dp)\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "#         # ages  =[1,1,2,2]\n",
    "#         # scores=[5,5,4,6]\n",
    "#         n = len(scores)\n",
    "#         ages = [[age, i] for i, age in enumerate(ages)]\n",
    "#         ages.sort(key=lambda x: (x[0], scores[x[1]]))\n",
    "#         # print(\"ages:\", ages)\n",
    "#         @cache\n",
    "#         def dfs(i: int) -> int:\n",
    "#             res_score = 0\n",
    "#             age_i, index_i = ages[i]\n",
    "#             for j in range(i):\n",
    "#                 age_j, index_j = ages[j]\n",
    "#                 if age_j < age_i and scores[index_j] > scores[index_i]:\n",
    "#                     continue\n",
    "#                 else:\n",
    "#                     res_score = max(res_score, dfs(j))\n",
    "#             # print(\"i:\", i, \", res_score:\", res_score+scores[index_i])\n",
    "#             return res_score + scores[index_i]\n",
    "        \n",
    "#         return max(dfs(i) for i in range(n))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        # scores=[4,5,5,6]\n",
    "        # ages  =[2,1,1,2]\n",
    "        n = len(scores)\n",
    "        scores = [[x, i] for i, x in enumerate(scores)]\n",
    "        scores.sort(key=lambda x: (x[0], ages[x[1]]))\n",
    "        # print(\"scores:\", scores)\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            score_i, index_i = scores[i]\n",
    "            res_score = 0\n",
    "            for j in range(i):\n",
    "                score_j, index_j = scores[j]\n",
    "                if ages[index_j] <= ages[index_i]:\n",
    "                    res_score = max(res_score, dfs(j))\n",
    "            # print(\"i:\", i, \", res_score:\", res_score)\n",
    "            return res_score + score_i\n",
    "\n",
    "        return max(dfs(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "本质是两个维度的LIS问题，首先按照年龄维度升序排序，如果年龄相同个，按照分数排序，然后\n",
    "分数维度单独独立出来作为序列X，求取X序列最大权值和非递减序列即可，DP可平方级复杂度求解\n",
    "'''\n",
    "\n",
    "from typing import List\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "\n",
    "        arr = [(a, b) for a, b in zip(ages, scores)]\n",
    "        arr.sort()\n",
    "\n",
    "        # 以i位置数值结尾的LIS最大和\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def dp(i):\n",
    "            if i == 0:\n",
    "                return arr[0][1]\n",
    "\n",
    "            ans = arr[i][1]\n",
    "            for ii in range(i-1, -1, -1):\n",
    "                if arr[ii][1] <= arr[i][1]:\n",
    "                    ans = max(ans, dp(ii) + arr[i][1])\n",
    "            return ans\n",
    "\n",
    "        ans = -1\n",
    "        for end_pos in range(len(scores)-1, -1, -1):\n",
    "            ans = max(ans, dp(end_pos))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        nums = list(zip(scores, ages))\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            ans= 0\n",
    "            for j in range(i):\n",
    "                if nums[j][1] <= nums[i][1]:\n",
    "                    ans = max(ans, dfs(j))\n",
    "            ans += nums[i][0]\n",
    "            return ans\n",
    "        \n",
    "        return max(dfs(i) for i in range(n))\n",
    "\n",
    "        # nums = sorted(zip(scores, ages))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        nums = sorted(zip(scores, ages), key=lambda x:(x[0], x[1]))\n",
    "        # 基于值域-朴素,ages=[1,1000]内\n",
    "        # dp[i]表示以元素 i 结尾的最长非减子序列的最高分数\n",
    "        # dp[i] = max(dp[j]) + score[i], j <= i对应的age元素\n",
    "        # 注意i可以取到age, 所以max操作要格外小心\n",
    "        # dp = [0] * (max(ages) + 1)\n",
    "        # for score, age in nums:\n",
    "        #     dp[age] = max(dp[i] for i in range(1, age + 1)) + score\n",
    "        # return max(dp)\n",
    "\n",
    "        # 基于值域-线段树,使用线段树优化max查询\n",
    "        ages = [item[1] for item in nums]\n",
    "        n = max(ages) + 1\n",
    "        mx = [0] * (4 * n)\n",
    "\n",
    "        def modify(o, l, r, idx, val):\n",
    "            if l == r:\n",
    "                mx[o] = val\n",
    "                return\n",
    "            mid = (l + r) // 2\n",
    "            if idx <= mid:\n",
    "                modify(2*o, l, mid, idx, val)\n",
    "            else:\n",
    "                modify(2*o+1, mid+1, r, idx, val)\n",
    "            mx[o] = max(mx[2*o], mx[2*o+1])\n",
    "        \n",
    "        def query(o, l, r, L, R):\n",
    "            if L <= l and r <= R:\n",
    "                return mx[o]\n",
    "            res = 0\n",
    "            mid = (l + r) // 2\n",
    "            if L <= mid:\n",
    "                res = query(2*o, l, mid, L, R)\n",
    "            if R > mid:\n",
    "                res = max(res, query(2*o+1, mid+1, r, L, R))\n",
    "            return res\n",
    "        \n",
    "        for score, age in nums:\n",
    "            age += 1\n",
    "            res = query(1, 1, n, 1, age) + score\n",
    "            modify(1, 1, n, age, res)\n",
    "    \n",
    "        return mx[1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        a2=[]\n",
    "        for pos,e in enumerate(ages):\n",
    "            a2.append([pos,e,scores[pos]])\n",
    "        a2.sort(key=lambda x:(x[1],x[2]))\n",
    "        d=dict()\n",
    "        def dfs(pos):\n",
    "            if pos in d:\n",
    "                return d[pos]\n",
    "            pos2=a2[pos][0]        \n",
    "            v=scores[pos2]\n",
    "            v2=0\n",
    "            for p2 in range(pos+1,len(a2)):\n",
    "                if a2[p2][1]==a2[pos][1]:\n",
    "                    r=dfs(p2)\n",
    "                    if r>v2:v2=r\n",
    "                if a2[p2][1]>a2[pos][1]:\n",
    "                    if scores[a2[p2][0]]>=v:\n",
    "                        r=dfs(p2)\n",
    "                        if r>v2:v2=r\n",
    "            d[pos]=v+v2\n",
    "            return v+v2\n",
    "        maxr=0\n",
    "        for pos in range(len(a2)):\n",
    "            r=dfs(pos)\n",
    "            if r>maxr:\n",
    "                maxr=r\n",
    "        return maxr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        zipp = sorted(zip(scores, ages))\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            res = 0\n",
    "            for j in range(i):\n",
    "                if zipp[j][1] <= zipp[i][1]:\n",
    "                    res = max(res, dfs(j))\n",
    "            return res + zipp[i][0]\n",
    "        \n",
    "        ans = 0\n",
    "        for ii in range(len(scores)):\n",
    "            ans = max(ans, dfs(ii))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        ls = sorted(zip(ages, scores))\n",
    "        @cache\n",
    "        def helper(i):\n",
    "            if i<0:\n",
    "                return 0\n",
    "            else:\n",
    "                ans = ls[i][1]\n",
    "                for j in range(i):\n",
    "                    if ls[j][0]<ls[i][0] and ls[j][1]>ls[i][1]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        ans = max(ans, helper(j)+ls[i][1])\n",
    "                return ans\n",
    "        return max(helper(i) for i in range(len(ls)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        # 矛盾是     age小的分数严格大于年龄大的分数\n",
    "        a = sorted(zip(scores,ages))\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            res = 0\n",
    "            for j in range(i):\n",
    "                if a[i][1] >= a[j][1]:\n",
    "                    res = max(res,dfs(j))\n",
    "            return res + a[i][0]\n",
    "        ans = 0\n",
    "        for i in range(len(a)):\n",
    "            ans = max(ans, dfs(i))\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        nums = list(zip(ages, scores))\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            ans= 0\n",
    "            for j in range(i):\n",
    "                if nums[j][1] <= nums[i][1]:\n",
    "                    ans = max(ans, dfs(j))\n",
    "            ans += nums[i][1]\n",
    "            return ans\n",
    "        \n",
    "        return max(dfs(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:\n",
    "        # 基于值域-线段树,使用线段树优化max查询\n",
    "        nums = sorted(zip(scores, ages), key=lambda x:(x[0], x[1]))\n",
    "        ages = [item[1] for item in nums]\n",
    "        n = max(ages) + 1\n",
    "        mx = [0] * (4 * n)\n",
    "\n",
    "        def modify(o, l, r, idx, val):\n",
    "            if l == r:\n",
    "                mx[o] = val\n",
    "                return\n",
    "            mid = (l + r) // 2\n",
    "            if idx <= mid:\n",
    "                modify(2*o, l, mid, idx, val)\n",
    "            else:\n",
    "                modify(2*o+1, mid+1, r, idx, val)\n",
    "            mx[o] = max(mx[2*o], mx[2*o+1])\n",
    "        \n",
    "        def query(o, l, r, L, R):\n",
    "            if L <= l and r <= R:\n",
    "                return mx[o]\n",
    "            res = 0\n",
    "            mid = (l + r) // 2\n",
    "            if L <= mid:\n",
    "                res = query(2*o, l, mid, L, R)\n",
    "            if R > mid:\n",
    "                res = max(res, query(2*o+1, mid+1, r, L, R))\n",
    "            return res\n",
    "        \n",
    "        for score, age in nums:\n",
    "            age += 1\n",
    "            res = query(1, 1, n, 1, age) + score\n",
    "            modify(1, 1, n, age, res)\n",
    "    \n",
    "        return mx[1]\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
